1. Field of the Invention
This invention relates to content addressable memories. More particularly, this invention relates to circuits and methods for determination of the priority of the selection of the index address based on programmed priority.
2. Description of Related Art
As is known in the art, a content addressable memory (CAM) has comparand data supplied to the memory and the memory returns an address if a corresponding match is found. The entire CAM can be searched in a single clock cycle and if a match is found, the address returned may be used to retrieve data associated with the search string. Such associated data is typically stored in a separate, discrete memory in a location specified by the result of the CAM search.
The structure and function of the CAM permits the determination of the best routing of messages on a network such as an intranet or the Internet. A router employs a CAM to quickly determine the location of the fast route for a message rather than a slower software based search through a standard memory array to determine the path.
Generally, when a comparand has multiple matches to locations within the CAM, a priority encoder selects the address or index of the location with the matching content and having the greatest priority dependent on the priority scheme implemented within the CAM. Generally the priority scheme used is fixed and not easily changeable in CAMs as manufactured at the present time.
Magnitude comparators are well known in the conventional art for determining the relative magnitude of two binary numbers. A general form of a magnitude comparator compares a group of most significant bits of the two binary numbers for equality and the next less significant bits if they are less than or greater than one another. All the groupings are then logically OR'ed to determine the relative magnitudes of the two binary numbers. The equality of the two binary numbers is determined by performing an exclusive NOR (XNOR) for each bit pair of the two binary numbers. The results of the XNOR's of each bit pair are then combined with a logical AND. Refer to FIG. 6 for a discussion of an example of a conventional structure of a magnitude comparator as presented in Digital Design, Mano, Prentice Hall PTR, Published 1991, pp. 163-165. Each of the exclusive NOR's U1, U2, U3, and U4 have a pair of bits (A3, B3), (A2, B2), (A1, B1), (A0, B0), respectively representing the digits of each of the two binary numbers connected as inputs. The exclusive NOR function as is known in the art is the function for equivalence in Boolean algebra and therefore each of the XNOR's U1, U2, U3, and U4 provides a signal indicating the equality of each of the pairs of bits (A3, B3), (A2, B2), (A1, B1), (A0, B0). The XNOR's U1, U2, U3, and U4 as is further known in the art has the Boolean function:An*Bn+ An* Bn
The XNOR's U1, U2, U3, and U4 each have two inverters I1 and I2 which provide the complement for each of the pairs of bits (A3, B3), (A2, B2), (A1, B1), (A0, B0). The AND gate I3 has the complement of the bit An and the bit Bn as inputs and the AND gate I4 has the bit An and the complement of the bit Bn as inputs. The output of the AND gate I3 provides the inequality An<Bn and the output of the AND gate I4 provides the inequality An>Bn. The inputs of the NOR gate I5 are the outputs of the AND gates I3 and I4. The output of the NOR gate I5 is the indication of the equality of the input bits (An, Bn).
The AND gates I6, I8, I10 combine the equality of the more significant bits and the inequality indicating An<Bn of the lesser significant bit. The outputs of the AND gates I6, I8, I10 are combined by the OR gate I13 to generate the inequality A<B of the two binary numbers.
The AND gates I7, I9, I11 combine the equality of the more significant bits and the inequality indicating An>Bn of the lesser significant bits. The outputs of the AND gates I7, I9, I11 are combined by the OR gate I14 to generate the inequality A>B of the two binary numbers.
The AND gate I12 has the equality outputs of XNOR's U1, U2, U3, and U4. Since all of the pairs of bits (A3, B3), (A2, B2), (A1, BI), (A0, B0) must be equal for the binary numbers to be equal, the output of the AND gate I12 provides the indication that all the pairs of bits (A3, B3), (A2, B2), (A1, B1), (A0, B0) are equal and therefore the indication of the equality of the two binary numbers.
The outputs F1, F2, F3 of the magnitude comparator provide individual or “one hot” indication of the relative magnitudes of the two binary numbers A and B. Having this conventional structure forces an implementation of the circuit to occupy excess area within an integrated circuit. While the structure of the magnitude comparator as shown is essentially a canonical structure, an actual circuit implementation would require more circuits than shown to implement the function. It is well known in the conventional art that basic function of a CMOS logic circuit is an inverter and that more complex functions formed are normally NAND gates or NOR gates. This requires use of inverted logic and thus extra inverters to accomplish a simple AND or OR function.
The implementation of an inequality function as an exclusive OR function using a passgate or transmission gate is explained in Mano pages 430-433 and shown in FIG. 7. The two input bits A and B are connected respectively to the inverter circuits I1 and I2 to provide the complements for the two input bits A and B. In this implementation, the control of the transmission gates TG1 and TG2 is determined by the state of the input bit A. The state of the input bit B or its complement at the output of the inverter I2 is the connected to transfer through the pass-gates TG1 or TG2 as controlled by the state of the input bit A. It is shown in Table 1 that the output F is the exclusive OR (XOR) of the two input bits A and B.
TABLE 1ABTG1TG2F00CLOSEDOPEN001CLOSEDOPEN110OPENCLOSED111OPENCLOSED0
It is well known in the conventional art that the exclusive OR as shown in Table 1 is a negative function of the XNOR or an equality function. Thus the function F of Table 1 can be represented as:F=(A≠B)= (A=B)
U.S. Pat. No. 5,602,550 (Stein) describes a method and apparatus for compressing a data vector of a predetermined number of data points. The apparatus includes a memory for storing the compressed data vector, a first comparator for determining a largest and smallest data point of the data vector and a second comparator for comparing the largest and smallest data point and when they are equal, causing a first data point of the data vector to be stored in the memory as the compressed data vector. The apparatus also includes a first processor for determining a data field width necessary to uniquely describe a largest relative magnitude data point and a second processor for storing the data points of the data vector as the compressed vector in data fields of memory of the data field width. The apparatus also includes a comparator and register for creating a difference vector of difference values of adjacent data points of the data vector, a first processor for determining a data field width necessary to uniquely describe a largest magnitude difference value of the difference vector, and a second processor for storing the difference points of the difference vector as the compressed vector in data fields of the memory of the determined field width along with a magnitude and sign of the first data point of the data vector.